package com.cqs.leetcode.bit;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;

import static java.util.stream.Collectors.toSet;

/**
 * @author lixiaowen
 * @create 2019-12-18
 */
public class CircularPermutationBinaryRepresentation1238 {

    public List<Integer> circularPermutation(final int n, int start) {
        int count = -1;
        int total = (1<<n);
        List<Integer> list = new ArrayList<>();
        start = gray2Decimal(start);
        while (++count < total ) {
            int val = (start + count) % total;
            list.add(toGray(val));
        }
        return list;
    }

    /**
     * 格雷码转(对应的数字)化普通十进制
     * @param gray
     * @return
     */
    private static int gray2Decimal(int gray){
        //转成格雷码 方便位计算
        int[] grayCode = toBinaryCode(gray);
        int result = grayCode[0];
        int preBinary = grayCode[0];
        for (int i = 1; i < grayCode.length; i++) {
            preBinary = preBinary ^ grayCode[i];
            result = result * 2 + preBinary;
        }
        return result;
    }

    private static int toGray(int n) {
        int[] bins = toBinaryCode(n);
        int result = bins[0] << 1;
        for (int i = 1; i < bins.length; ++i) {
            result = (result << 1) +  (bins[i] ^ bins[i - 1]);
        }
        //转化为十进制
        return result;
    }

    private static int[] toBinaryCode(int n) {
        //bins[0]表示最高为bins[31]为最低位
        int[] bins = new int[32];
        for (int i = 0; i < bins.length; ++i) {
            bins[i] = (n >> (bins.length - 1 - i)) & 0x1;
        }
        return bins;
    }


    public static void main(String[] args) {
        CircularPermutationBinaryRepresentation1238 rep = new CircularPermutationBinaryRepresentation1238();
        int n = 5;
        int start = 1 + new Random().nextInt(n) ;
        System.out.println(n + "\t" + start);
        List<Integer> list = rep.circularPermutation(n, start);
        System.out.println(list);
        System.out.println(list.stream().collect(toSet()).size());
    }
}
